nition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int asum = 1;
        int bsum = 1;
        int df=0;
        while(curA!=nullptr)
        {
            curA=curA->next;
            asum++;
        }
        while(curB!=nullptr)
        {
            curB=curB->next;
            bsum++;
        }

        curA = headA;
        curB = headB;
        if(asum>bsum)
        {
            df = asum-bsum;
            while(df--){
                if(curA!=nullptr && curA->next!=nullptr)
                curA = curA->next;
            }
        }
        else
        {
            df = bsum-asum;
            while(df--){
                if(curB!=nullptr && curB->next!=nullptr)
                curB = curB->next;
            }
        }
        while(curA!=nullptr){
            if(curA==curB)
            return curA;
            else
            {
                curA = curA->next;
                curB = curB->next;
            }
        }
        return nullptr;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
        return nullptr;
        ListNode* prev = nullptr,*cur = head,*next = head->next;
        while(cur!=nullptr){
            cur->next = prev;
            prev = cur;
            cur = next;
            if(next!=nullptr)
            next = next->next;
        }
        return prev;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head,int count){
        ListNode* prev=nullptr;
        ListNode* cur = head;
        ListNode* next =head->next;
        int size=0;
        while(size<count){
            size++;
            cur->next = prev;
            prev = cur;
            cur = next;
            if(next->next!=nullptr)
            next = next->next;
        }
        return prev;
    }

    bool isPalindrome(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
        return true;

        int sum = 0;
        ListNode* cur = head;
        while(cur!=nullptr){
            sum++;
            cur=cur->next;
        }
        int flag =0;
        if(sum%2==0)//==0走 sum/2 !=0走sum/2+1
        {
            sum = sum/2;
        }
        else
        {
            flag=1; //B要多走一步
            sum = sum/2+1;
        }
        ListNode* curA = head;
        int tmp = sum;
        while(tmp--)
        {
            curA = curA->next;
        }

        ListNode* curB = reverse(head,sum);
        if(flag)
        curB=curB->next;
        
        while(curA!=nullptr && curB!=nullptr)
        {
            if(curA->val != curB->val)
            break;

            curA = curA->next;
            curB = curB->next;
        }
        if(curA==nullptr && curB==nullptr)
        return true;
        else
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=nullptr && fast->next!=nullptr && fast->next->next!=nullptr)
        {
            slow = slow->next;
            if(fast!=nullptr && fast->next!=nullptr && fast->next->next!=nullptr)
            fast = fast->next->next;
            if(slow==fast)
            return true;
        }
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=nullptr && fast->next!=nullptr && fast->next->next!=nullptr)
        {
            slow = slow->next;
            if(fast!=nullptr && fast->next!=nullptr && fast->next->next!=nullptr)
            fast = fast->next->next;
            if(slow==fast)
            return fast;
        }
        return nullptr;
    }

    ListNode * detectCycle(ListNode *head) {
        ListNode* ret = hasCycle(head);
        if(ret == nullptr)
        return nullptr;
        
        ListNode* cur = head;
        while(cur!=ret)
        {
            cur=cur->next;
            ret=ret->next;
        }
        return ret;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr)
        return list2;
        if(list2==nullptr)
        return list1;

        ListNode* head,*cur1,*cur2,*cur;
        if(list1->val<list2->val)
        {
            head = list1;
            cur1 = list1->next;
            cur2 = list2;
        }
        else
        {
            head = list2;
            cur1 = list1;
            cur2 = list2->next;
        }
        cur = head;

        while(cur1!=nullptr && cur2!=nullptr)
        {
            if(cur1->val<cur2->val){
                cur->next = cur1;
                cur1=cur1->next;
            }else{
                cur->next = cur2;
                cur2=cur2->next;
            }
            cur=cur->next;
        }
        if(cur1==nullptr)
        cur->next = cur2;
        if(cur2==nullptr)
        cur->next = cur1;

        return head;
    }
};


